package class02

import (
	"math"
	"traning/algorithm/utility"
)

func needMin(matrix [][]int) int {
	return utility.Max(1, needMinProcess(matrix, 0, 0))
}

func needMinProcess(matrix [][]int, i, j int) int {
	// 到了最后一个位置，需要返回当前位置需要的最少血量
	if i == len(matrix)-1 && j == len(matrix[0]) - 1  {
		if matrix[i][j] > 0 {
			return 1
		} else {
			return -matrix[i][j] + 1
		}
	}

	p1, p2 := math.MaxInt,  math.MaxInt
	if i+1 < len(matrix) {
		p1 = needMinProcess(matrix, i+1, j)
	}
	if j+1 < len(matrix[0]) {
		p2 = needMinProcess(matrix, i, j+1)
	}
	return utility.Max(1, utility.Min(p1, p2) - matrix[i][j])
}

func needMinDp(matrix [][]int) int {
	row := len(matrix)-1
	col := len(matrix[0])-1
	// 初始化 dp 表
	dp := make([][]int, row+1)
	for i:=0; i<len(dp); i++ {
		dp[i] = make([]int, col+1)
	}

	// 根据递归终止条件，填写 base case
	if matrix[row][col] > 0 {
		dp[row][col] = 1
	} else {
		dp[row][col] = -matrix[row][col] + 1
	}
	// 填写最右边那列
	for r:=row-1; r>=0; r-- {
		dp[r][col] = utility.Max(1, dp[r+1][col]-matrix[r][col])
	}
	// 填写最底下的行
	for c:=col-1; c>=0; c-- {
		dp[row][c] = utility.Max(1, dp[row][c+1]-matrix[row][c])
	}
	// 每个位置依赖右边和下边
	// 所以填dp表的顺序，从右往左，从下到上
	for r:=row-1; r>=0; r-- {
		for c:=col-1; c>=0; c-- {
			dp[r][c] = utility.Max(1, utility.Min(dp[r+1][c], dp[r][c+1]) - matrix[r][c])
		}
	}

	return dp[0][0]
}